#include "data.h"
#include "Activity.h"
#include "global.h"

int backtrack( schedule &ms, 
			  deque <Activity> &acts, 
			  int delta,
			  deque <int> av, 
			  int first, 
			  int stage,
			  bool ahead,	
			  int alpha,
			  int &maxWait
			  ) 
{
	int  i ,j, k, tmpav,  tmpk, machine ;
	deque <int>   wait;	

	for ( i = 0; i < ms.getnbSched(); i ++ ) {		
		for ( k = 0; k < ms.getnbStages(); k ++ ) {		
			wait.push_back(0);
		}		
	}
	
	i = ms.getSched(first);

	if ( first < ms.getnbSched()  && stage < ms.getnbStages()  ) {
		
		//set up release time
		if ( stage== 0) 
			acts[i * ms.getnbStages() + stage].setRtime(i, stage, 0);
		else
			acts[i * ms.getnbStages() + stage].
			setRtime(i, stage, acts[i * ms.getnbStages()
			+ stage-1].getEtime(i,stage-1) );

		//FAM

		tmpav = RAND_MAX;		
		for ( k = stage * ms.getnbMachinesPerStage(); 
		k < stage * ms.getnbMachinesPerStage() + 
			ms.getnbMachinesPerStage(); k ++) {

			if (tmpav > av[k]) { 
				tmpav = av[k];
				tmpk  = k;
			}
		}	


		acts[i * ms.getnbStages() + stage].
			setEStime( i, stage, max(acts[i * ms.getnbStages() 
			+ stage].getRtime(i, stage), tmpav));	

			acts[i * ms.getnbStages() + stage].
				setStime ( i, stage, 
				acts[i * ms.getnbStages() + stage].
				getEStime(i,stage) + ahead * delta   );





		//compute waiting time and the maximum among them
		wait[i * ms.getnbStages() + stage ] = 
			acts[i * ms.getnbStages() + stage].
			getStime(i, stage) - acts[i * ms.getnbStages() 
			+ stage].getRtime(i, stage) ;
		wait[i * ms.getnbStages() + 0 ] = 0;	


		maxWait = 0;
		if ( maxWait < wait[i * ms.getnbStages() + stage ] )
			maxWait = wait[i * ms.getnbStages() + stage ];
		
		delta = wait[i * ms.getnbStages() + stage ] - alpha; 
		delta = max( delta, 0);	

		//backtracking


		if ( delta <= 0) {

			//define av
			av[tmpk] = acts[i * ms.getnbStages() + stage].
				getEtime( i, stage);
			
			acts[i * ms.getnbStages() + stage].
				setMachine( i, stage, tmpk);

	
			stage = stage +1;

			ahead = 0;
			
			backtrack( ms, acts, delta, av, first, stage, 
				ahead, alpha,  maxWait);
		
		}else {

			machine = acts[i * ms.getnbStages() + stage - 1].
				getMachine( i, stage - 1 );

			av[machine] = acts[i * ms.getnbStages() + stage - 1].
				getEtime( i, stage - 1 ) - 
				acts[i * ms.getnbStages() + stage - 1].
				getPtime( i, stage - 1);
		

			stage = stage - 1;
			ahead = 1;
			backtrack( ms, acts, delta, av, first, stage, 
				ahead, alpha,  maxWait);
		}
	
	}else if ( first < ms.getnbSched() ) {

		stage = 0;

		first = first + 1;

		backtrack( ms, acts, delta, av,	first, stage, 
			ahead, alpha, maxWait);		
	}

		int makespan = 0;
		for ( i = 0; i < ms.getnbSched(); i ++ ) {	
			for ( j = 0; j < ms.getnbStages(); j ++ ) {
				if ( makespan < 
					acts[i * ms.getnbStages() + j].getEtime(i,j))
					makespan = acts[i * ms.getnbStages() + j].
					getEtime(i,j) ;
			}		
		}
		
	return makespan;
}